from tools_algorithm import *


class Solution:
    def numberOfSpecialChars(self, word: str) -> int:
        a = [0] * 26
        b = [0] * 26

        for w in word:
            if "a" <= w and w <= "z":
                a[ord(w) - ord("a")] += 1
            else:
                b[ord(w) - ord("A")] += 1
        ans = 0

        for i in range(26):
            ans += min(min(a[i], b[i]), 1)
        return ans


class Solution:
    def numberOfSpecialChars(self, word: str) -> int:
        a = [inf] * 26
        b = [-1] * 26
        ans = 0
        for i, w in enumerate(word):
            if "a" <= w and w <= "z":
                a[ord(w) - ord("a")] = i
            elif b[ord(w) - ord("A")] == -1:
                b[ord(w) - ord("A")] = i
        for i in range(26):
            if a[i] < b[i]:
                ans += 1
        return ans


s = Solution()
print(s.numberOfSpecialChars("AbBCab"))


class Solution:
    def minimumOperations(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        cnt = [[0] * 10 for _ in range(n)]
        for i in range(n):
            for j in range(m):
                cnt[i][grid[j][i]] += 1
        f = [[0] * 10 for _ in range(n)]
        for i in range(n):
            for j in range(10):
                mn = 0
                if i > 0:
                    mn = inf
                    for k in range(10):
                        if k != j:
                            mn = min(f[i - 1][k], mn)
                f[i][j] = mn + (m - cnt[i][j])
        return min(f[n - 1][k] for k in range(10))


class Solution:
    def findAnswer(self, n: int, edges: List[List[int]]) -> List[bool]:
        h = DefaultDict(list)
        for a, b, w in edges:
            h[a].append([b, w])
            h[b].append([a, w])

        def f(s):
            st = [inf] * n
            st[s] = 0
            q = [[0, s]]
            while q:
                v, a = heappop(q)
                if v == st[a]:
                    for b, w in h[a]:
                        if w + v < st[b]:
                            st[b] = v + w
                            heappush(q, [v + w, b])
            return st

        st = f(0)
        ts = f(n - 1)
        mn = ts[0]
        ans = []
        for a, b, w in edges:
            if mn < inf and (st[a] + w + ts[b] == mn or st[b] + w + ts[a] == mn):
                ans.append(True)
            else:
                ans.append(False)
        return ans


s = Solution()
print(s.findAnswer(3, [[2, 1, 6]]))
